package pers.qianyu.month_202012.date_20201214;

import org.junit.*;

/**
 * [模糊]
 * 376. 摆动序列
 * https://leetcode-cn.com/problems/wiggle-subsequence/description/
 *
 * @author mizzle rain
 * @date 2020-12-14 15:17
 */
public class WiggleMaxLength {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null) {
            return 0;
        }
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        int[] up = new int[len];
        int[] down = new int[len];
        up[0] = 1;
        down[0] = 1;
        for (int i = 1; i < len; i++) {
            if (nums[i] > nums[i - 1]) {
                up[i] = Math.max(down[i - 1] + 1, up[i - 1]);
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {
                down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
                up[i] = up[i - 1];
            } else {
                down[i] = down[i - 1];
                up[i] = up[i - 1];
            }
        }
        return Math.max(up[len - 1], down[len - 1]);
    }

    @Test
    public void test1() {
        int[] arr = {1, 7, 4, 9, 2, 5};
        int result = new WiggleMaxLength().wiggleMaxLength(arr);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        int[] arr = {1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
        int result = new WiggleMaxLength().wiggleMaxLength(arr);
        System.out.println("result = " + result);
    }

    @Test
    public void test3() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int result = new WiggleMaxLength().wiggleMaxLength(arr);
        System.out.println("result = " + result);
    }
}
